import java.util.Deque;
import java.util.LinkedList;

class Checkout {
    /**
     * 本题过于简单，就是简单维护一个单调队列即可，是我太过期待了*/

    public Checkout() {
        
    }

    // 创建双端队列维护有效区间的最大值
    public Deque<int[]> queue = new LinkedList<>();

    // 创建数组当作队列，使用下标维护区间
    int[] arr = new int[1_00001];
    int left = 0;
    int right = 0;

    public int get_max() {
        /**
         * 获取结算商品中的最高价格*/
        if(queue.isEmpty()) {
            return -1;
        } else {
            return queue.peekFirst()[0];
        }
    }
    
    public void add(int value) {
        /**
         * 尾插*/
        // 1 入队
        arr[right++] = value;

        // 2 维护单调队列
        while(!queue.isEmpty() && queue.peekLast()[0] <= value) {
            queue.pollLast();
        }
        queue.offerLast(new int[]{value, right-1});
    }
    
    public int remove() {
        /**
         * 头删*/
        // 1 判空
        if(left == right) {
            return -1;
        }

        // 2 删除
        left ++;

        // 3 维护队列
        while(!queue.isEmpty() && queue.peekFirst()[1] < left) {
            queue.pollFirst();
        }
        return arr[left-1];
    }
}

/**
 * Your Checkout object will be instantiated and called as such:
 * Checkout obj = new Checkout();
 * int param_1 = obj.get_max();
 * obj.add(value);
 * int param_3 = obj.remove();
 */